package com.dmall.algorithm.chapter01;

/**
 * 暴力解法，时间复杂度是O(n^3)
 */
public class Leetcode84V1 {

    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        if (heights.length == 1) {
            return heights[0];
        }
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int minHeight = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    minHeight = Math.min(minHeight, heights[k]);
                }
                int curArea = (j - i + 1) * minHeight;
                maxArea = Math.max(maxArea, curArea);
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
         int[] heights = {0, 9};
//        int[] heights = {6, 7, 5, 2, 4, 5, 9, 3};
        Leetcode84V1 leetcode84 = new Leetcode84V1();
        System.out.println(leetcode84.largestRectangleArea(heights));
    }
}
